/*
 * @lc app=leetcode.cn id=81 lang=cpp
 *
 * [81] 搜索旋转排序数组 II
 */

// @lc code=start
class Solution {
public:
    bool search(vector<int>& nums, int target) {
        int n = nums.size();
        if (!n) {
            return false;
        }
        if (n == 1) {
            return nums[0] == target ? true : false;
        }
        int l1 = 0,r1;
        int l2,r2 = nums.size()-1;
        for(int i = 0;i < nums.size()-1;i++) {
            if(nums[i] > nums[i+1]) {
                l2 = i+1;
                r1 = i;
                break;
            }
        }
        while(l1 <= r1) {
            int mid = (l1 + r1)/2;
            if(target == nums[mid]) {
                return true ;
            } else if(target < nums[mid]) {
                r1 = mid - 1;
            } else {
                l1 = mid + 1;
            }
        }
        while(l2 <= r2) {
            int mid = (l2 + r2)/2;
            if(target == nums[mid]) {
                return true ;
            } else if(target < nums[mid]) {
                r2 = mid - 1;
            } else {
                l2 = mid + 1;
            }
        }
        return false ;
    }
};
// @lc code=end

